package com.agile.leetcode.easy.kthLargest;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一棵二叉搜索树，请找出其中第k大的节点。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: root = [3,1,4,null,2], k = 1
 * 3
 * / \
 * 1   4
 * \
 * 2
 * 输出: 4
 * <p>
 * 示例 2:
 * <p>
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 * 5
 * / \
 * 3   6
 * / \
 * 2   4
 * /
 * 1
 * 输出: 4
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author KD
 * @Date 2021/3/4 15:07
 */
public class KthLargest {
    // 定义集合接收数据
    List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        KthLargest kthLargest = new KthLargest();

    }

    public int kthLargest(TreeNode root, int k) {
        // 对root进行中续遍历
        inOrderTranverse(root);
        return list.get(list.size() - k);
    }

    private void inOrderTranverse(TreeNode root) {
        if (root.left != null) {
            inOrderTranverse(root.left);
        }
        // 将操作的数字加入集合
        list.add(root.val);
        if (root.rigth != null) {
            inOrderTranverse(root.rigth);
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode rigth;

    public TreeNode(int val) {
        this.val = val;
    }
}
